## 利用多线程对比各类排序算法的排序速度
## 已完成的排序算法：
## 1.快速排序  2.冒泡排序  3.选择排序

import time
import datetime
import random
import threading
import sys

## generate random array[]
def GetRandomArray(arrayLength = 100, maxValue = 10000):
	randomArray = []
	for i in range (0, arrayLength):
		randomArray.append(random.randint(0, maxValue))
	return randomArray

## bubble sort
def BubbleSort(array):
	for i in range(0, len(array)):
		for j in range(0, len(array) - i - 1):
			if (array[j] > array[j + 1]):
				array[j], array[j + 1] = array[j + 1], array[j]
	return array

## QuickSort
def QuickSort(array):
	quickSort(array, 0, len(array) - 1)
	return array

def quickSort(array, start, end):
	if(start >= end):
		return
	index = Partition(array, start, end)
	quickSort(array, start, index - 1)
	quickSort(array, index + 1, end)
	return array

def Partition(array, start, end):
	left = start
	right = end
	pivot = array[end]
	while (left < right):
		while (left < right and array[left] <= pivot):
			left += 1
		while (left <right and array[right] >= pivot):
			right -= 1
		array[left], array[right] = array[right], array[left]
	array[left], array[end] = array[end], array[left]
	return left

## SelectionSort
def SelectionSort(array):
	for i in range(len(array)):
		minIndex = i
		for j in range(i + 1, len(array)):
			if (array[minIndex] > array[j]):
				minIndex = j
		array[i], array[minIndex] = array[minIndex], array[i]
	return array

## threading
class mythread(threading.Thread):
	"""docstring for mythread"""
	def __init__(self, threadID, name, array, oldArray):
		super(mythread, self).__init__()
		self.threadID = threadID
		self.name = name
		self.array = array
		self.oldArray = oldArray

	def run(self):
		newArray = []
		print('Start %sing...' %self.name)
		threadLock.acquire()
		time_start = datetime.datetime.now()
		newArray = ChoseSort(self.name, self.array)
		time_stop = datetime.datetime.now()
		time_cost = time_stop - time_start
		timeCosts.append('%s time cost: %s' %(self.name, time_cost))
		CheckResult(self.name, newArray, self.oldArray)
		threadLock.release()

def ChoseSort(threadName, array):
	newArray = []
	if (threadName == 'BubbleSort'):
		newArray = BubbleSort(array)
	elif (threadName == 'QuickSort'):
		newArray = QuickSort(array)
	elif (threadName == 'SelectionSort'):
		newArray = SelectionSort(array)
	else:
		print('There is no such sortmethod.')
	return newArray

def CheckResult(sortName, newArray, oldArray):
	errorFlag = 0
	print('Confirming...')
	for i in range(0, len(newArray) - 1):
		if (newArray[i] > newArray[i + 1]):
			print('Wrong sorting!')
			errorFlag = 1
			break
	if(len(set(newArray)) != len(set(oldArray))):
		print('Sort Error!  Array has been changed.')
		print('#===================================#')
		errorFlag = 1
	if not errorFlag:
		print('%s accomplished!' %sortName)
		print('#===================================#')

def PrintArray(array):
	for i in range(len(array)):
		print(array[i])

def WriteResult(arrayLength, timeCosts):
	strTimeCost = []
	for each in timeCosts:
		strTemp = each + '\n'
		strTimeCost.append(strTemp)
	strTimeCost.append('\n')
	with open('SortResult.txt', 'a', encoding = 'utf-8') as file:
		file.write(str(datetime.datetime.now()) + '\n')
		file.write('The length of array[] is %d' %arrayLength)
		file.writelines(strTimeCost)

if __name__ == '__main__':
	sortArray = []
	arrayLength = 8000
	maxValue = 1000000
	array = []
	newArray = []
	sortNames = ['QuickSort', 'BubbleSort', 'SelectionSort']
	threadIDs = []
	timeCosts = []
	sortArray = GetRandomArray(arrayLength, maxValue)
	threadLock = threading.Lock()

	print('Start...')
	print('The length of array[] is %d' %arrayLength)
	print('#===================================#')
	for i in range(len(sortNames)):
		threadIDs.append(i + 1)
		array = sortArray.copy()
		threadIDs[i] = mythread(i + 1, sortNames[i], array, array.copy())
		threadIDs[i].start()
		threadIDs[i].join()
	for each in timeCosts:
		print(each)
